



<HTML>

<HEAD>

<LINK rel="stylesheet" href="../exer.css">

</HEAD>

<BODY>

<H1>

Data Structures, Algorithms, & Applications in C++<BR>

Chapter 15, Exercise 9<BR>

<BR>

</H1>



We shall make use of the identity

<em class=var>(sum from i=1 to n)i<sup>2</sup>  = n(n+1)(2n+1)/6.

<br><br>

(sum from s=1 to q-1)s(q-s+1)<br>

= (q+1)(sum from s=1 to q-1)s - (sum from s=1 to q-1)s<sup>2</sup><br>

= (q+1)q(q-1)/2 - (q-1)q(2q-1)/6<br>

= q(q-1)(3q+3-2q+1)/3<br>

= q(q-1)(q+4)/3<br>

= Theta(q<sup>3</sup>)</em>







</FONT>

</BODY>

</HTML>

